package demo1;

public class DynamicPlanningPractise {
    /**
     * 盈利计划 - 二维费用背包问题，较困难*/
    public int profitableSchemes(int n, int m, int[] g, int[] p) {
        //n 代表人数 m 代表最低总利润 g代表每种工作所需人数 p代表每种工作利润
        /**
         有题目解析可得，本题是一个背包问题，于是我们可以根据这一提示进行解题
         题目要求我们使得人数<=n 并且 利润>=m时，此时所有的工作分配计划，先做
         状态表示：
         dp[i][j][k] 表示在挑选前i种工作时，满足总人数小于等于n 并且 总利润大于等于m，此时分配计划总和
         状态转移方程：
         根据最后一个元素的状态进行划分问题
         最后一个工作不选：dp[i][j][k] = dp[i-1][j][k]
         最后一个工作选：需要满足 j>=g[i](所需人数少于限制人数) dp[i][j][k] = dp[i-1][j-g[i]][max(0,k-p[i])]
         最后之所以那样写，是因为在本题中，我们需要满足的是利润至少为k，若是最后一个元素利润已经大于k，那么我们可以认为前面任选即可
         若是前面利润不大于k，则我们再去找组合大于k的
         目前问题：如何表示利润大于等于m这一条件，当前物品可以和其他利润一起加起来大于等于m，也可单独大于等于m，故有点没有思绪
         初始化：
         使用虚拟位置进行初始化，i表示0工作，没有工作那就没有利润，即dp[0][][0],此时无论人数限制多少，我们选择一个空集即可
         即是dp[0][j][0] = 1,j∈[0,n]
         需要注意下标的映射关系
         填表顺序：
         i从下到大填表*/
        int len = g.length;
        int MOD = 1000000000+7;
        //1 创建dp表
        int[][][] dp = new int[len+1][n+1][m+1];
        //2 初始化
        for(int j = 0; j <= n; j++)
            dp[0][j][0] = 1;
        //3 填表
        for(int i = 1; i <= len; i++) {
            for(int j = 0; j <= n; j++) {
                for(int k = 0; k <= m; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j>=g[i-1])
                        dp[i][j][k] += dp[i-1][j-g[i-1]][Math.max(0,k-p[i-1])];
                    dp[i][j][k]%=MOD;
                }
            }
        }
        //4 返回值
        return dp[len][n][m];
    }

    /**
     * 盈利计划 - 使用滚动数组进行优化
     * 时间复杂度O（n*n*n）
     * 空间复杂度O（n*n）*/
    public int profitableSchemesOther(int n, int m, int[] g, int[] p) {
        int len = g.length;
        int MOD = 1000000000+7;
        //1 创建dp表
        int[][] dp = new int[n+1][m+1];
        //2 初始化
        for(int j = 0; j <= n; j++)
            dp[j][0] = 1;
        //3 填表
        for(int i = 1; i <= len; i++)
            //使用滚动数组进行优化时，需要注意更改内部填表顺序
            for(int j = n; j >=g[i-1]; j--)
                for(int k = m; k >= 0; k--) {
                    dp[j][k] += dp[j-g[i-1]][Math.max(0,k-p[i-1])];
                    dp[j][k]%=MOD;
                }
        //4 返回值
        return dp[n][m];
    }

    /**
     * 组合个数Ⅳ - 实则为排列*/
    public int combinationSum4(int[] nums, int target) {
        /**
         由题及其示例可得：
         1，数组nums中的元素可以多次使用
         2，相同的元素，其相对位置不同，也可视作一个组合 - 在数学中我们对这种性质称之为排列而不是组合
         由于性质2，故我们无法使用背包问题的思路对其进行解决，因为背包问题所解决的是有限制条件下的组合问题
         状态表示：
         由于不是背包问题，故我们直接使用最常见的方式设定状态表示，即直接根据题目要求设定，如下：
         dp[i]表示凑成总和为i，一共有多少种排列数
         状态转移方程：
         依旧根据最后一个元素的状态进行划分问题
         当我们在最后一个位置选择nums[j]时，需要满足i>=nums[j]，此时dp[i] = dp[i-nums[j]]
         因为最后一个元素已选nums[j]，我们接下来只需要在元素总和为 i-nums[j] 的后面都添上一个nums[j]即可
         初始化：
         使用虚拟位置法进行初始化
         dp[0]表示 凑成元素总和为0，一共有多少排列数，我们仅能选择空集，故dp[0]=1
         */
        int n = nums.length;
        //1 创建dp表
        int[] dp = new int[target+1];
        //2 初始化
        dp[0] = 1;
        //3 填表
        for(int i = 1; i <= target; i++)
            for(int j = 0; j < n; j++)
                if(i>=nums[j])
                    dp[i]+=dp[i-nums[j]];
        //4 返回值
        return dp[target];
    }

    /**
     * 不同的二叉搜索树*/
    public int numTrees(int n) {
        /**
         二叉搜索树：左子树均小于根节点，右子树均大于根节点 */
        //1 创建dp表
        int[] dp = new int[n+1];
        //2 初始化
        dp[0] = 1;
        //3 填表
        for(int i = 1; i <= n; i++)//外层循环表示元素个数，也代表当前最大节点值
            for(int j = 1; j <= i; j++)//内层循环j表示根节点
                dp[i] += dp[j-1]*dp[i-j];
        //4 返回值
        return dp[n];
    }

    /**
     * 斐波那契数列模型 归纳总结*/
    public int numDecodings(String s) {
        //不使用优化进行dp
        //预处理
        char[] chars = s.toCharArray();
        int n = chars.length;

        //处理边界情况
        if(chars[0]=='0') return 0;// -- 首字母为0，则不可能解码
        if(n==1) return 1; // -- 若是仅有一个字符，特判

        //1 创建dp表 - 状态表示为 dp[i]表示 编译前i个数字的解码总数
        int[] dp = new int[n];
        //2 初始化
        dp[0] = 1;
        dp[1] += chars[1] != 0 ? 1 : 0;
        int tmp = (chars[0] - '0')*10 + (chars[1] - '0');
        dp[1] += tmp>=10 && tmp<= 26 ? 1 : 0;
        //3 填表
        for(int i = 2; i < n; i++) {
            dp[i] = chars[i]!=0 ? dp[i-1] : 0;
            tmp = (chars[i-1] - '0')*10 + (chars[i] - '0');
            dp[i] += tmp>=10 && tmp<= 26 ? dp[i-2] : 0;
        }
        //4 返回值
        return dp[n-1];
    }

    /**
     * 路径问题 归纳总结*/
    public int uniquePaths(int m, int n) {
        /**
         我们将机器人当前所处的位置坐标设定为（0，0） ，那么终点处的坐标即为（m-1，n-1）
         已知机器人只能向下或者向左移动，那么反过来思考
         当我们对dp[i][j]位置进行填表时，其上一个位置仅可能是dp[i-1][j] 或者 dp[i][j-1]

         状态表示：
         dp[i][j]表示以（i，j）下标为终点时，路径的总和
         状态转移方程：
         dp[i][j] = dp[i-1][j]+dp[i][j-1]
         初始化：
         由状态转移方程可得，当我们对x位置进行填表时，其依赖于上方及其左边的状态
         故当对第一行 第一列进行填表时，都会发生越界访问的情况
         使用虚拟位置法进行初始化，多创建一行、一列，只需将dp[1][0] = 1 或 dp[0][1] = 1即可*/
        //1 创建dp表 - 虚拟位置法
        int[][] dp = new int[m+1][n+1];
        //2 初始化
        dp[1][0] = 1;
        //3 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        //4 返回值
        return dp[m][n];
    }

    /**
     * 路径问题-地下城游戏
     * 之所以再做这一题，主要是因为其状态表示为以xx为起点*/
    public int calculateMinimumHP(int[][] dungeon) {
        /**
         对于本题，我还是有一点优势的，毕竟我已经知道了其状态表示的定义方式
         状态表示：
         dp[i][j]表示以（i，j）下标为起点时，能够拯救公主所需的最低初始健康值
         状态转移方程：
         我们需要满足两个条件，
         一，当前健康点数能够保证我们能够顺利走出当前房间
         二，走出当前房间后，所剩余的健康点数能够支持我们拯救公主
         综上，得表达式：dp[i][j] + dungeon[i][j] >= min(dp[i+1][j],dp[i][j+1])
         为了使得其为最低健康点数，故取等 再移项后得：
         dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j]
         此时我们还需要对dungeon[i][j]进行讨论：
         当其是负数时，min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j]也是一个正数,
         此时代表从（i，j）到终点所需的最低体力值

         当其等于零时，与上同理

         当其等于正数且该正数大于 min(dp[i+1][j],dp[i][j+1])时，此时其计算出来的值就会是一个负数，
         结合题意，就是说，当我们走到此处时即是健康值已经是负数，但通过这个巨大的血包，我们还是能拯救公主
         很显然这并不符合题意，故我们需要进行特判，当其计算的值为负数时，我们将其换为1
         意思就是，走到这里时，即是你只有1滴血，但是经过这个大血包后，我们依旧可以拯救公主
         综上所述，dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j],再进行特判，如果dp[i][j]<=0,则dp[i][j] = 1
         初始化：
         由于状态转移方程依赖于下、右两个位置的状态，故为了防止越界访问，我们使用虚拟位置法进行初始化
         在下面对创建一行，右边多创建一列
         虚拟位置赋值：
         将其全部设置为无穷大，仅将dp[m-1][n] = 1,表示出房间后至少还要剩一点健康值
         填表顺序：
         从下到上，从右到左*/
        // m 表示行 n 表示列
        int m = dungeon.length;
        int n = dungeon[0].length;
        int MAX = 0x3f3f3f3f;
        //1 创建dp表 - 虚拟位置法
        int[][] dp = new int[m+1][n+1];
        //2 初始化
        for(int k = 0; k <= n; k++)
            dp[m][k] = MAX;
        for(int k = 0; k <= m-2; k++)
            dp[k][n] = MAX;
        dp[m-1][n] = 1;
        //3 填表
        for(int i = m-1; i >= 0; i--) {
            for(int j = n-1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
                if(dp[i][j]<=0) dp[i][j] = 1;
            }
        }
        //4 返回值
        return dp[0][0];
    }

    /**
     * 打家劫舍系列问题-归纳总结*/
    public int massage(int[] nums) {
        /**
         由于每一个预约都有两种选择，接/不接
         故我们需要创建一个二维的dp表进行表示
         状态表示：
         dp[i][0] 表示第i个预约不接，此时最长预约时间
         dp[i][1] 表示第i个预约接受，此时最长预约时间
         状态转移方程：
         类似于打家劫舍的问题，我们一般都是根据最后一个元素的状态进行划分问题
         1 最后一个位置不接：那么dp[i-1][]可选择接也可选择不接，dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1])
         2 最后一个位置接受，那么dp[i-1][]必定不能接受，故dp[i][1] = dp[i-1][0] + nums[i](加上本次预约的时长)
         初始化：
         由状态转移方程可得，其可能会出现越界访问的情况，直接对dp[0][0] 和 dp[0][1]进行初始化
         */
        int n = nums.length;
        //处理边界情况
        if(n==0) return 0;
        //1 创建dp表
        int[][] dp = new int[n][2];
        //2 初始化
        dp[0][1] = nums[0];
        //3 填表
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        //4 返回值
        return Math.max(dp[n-1][0],dp[n-1][1]);
    }



    /**
     * 打家劫舍Ⅱ*/
    public int rob(int[] nums) {
        int n = nums.length;
        //对边界情况进行处理，若是元素小于等于三个，选出最大值即可
        if(n <= 3) {
            int ret = 0;
            for(int i = 0; i < n; i++)
                ret = Math.max(ret,nums[i]);
            return ret;
        }
        /**
         对偷1或者不偷1进行分类讨论即可 */
        int selectZero = branch(2,n-2,nums) + nums[0];
        int uncheckZero = branch(1,n-1,nums);
        return Math.max(selectZero,uncheckZero);
    }
    private static int branch(int begin, int end, int[] nums) {
        /**
         打家劫舍 - 需要对begin 和 end进行判定
         状态表示：
         dp[i][0]表示不选i下标元素时，最高金额
         dp[i][1]表示选择i下标元素时，最高金额
         状态转移方程：
         dp[i][0] = max(dp[i-1][0],dp[i-1][1])
         dp[i][1] = dp[i-1][0] + nums[i]
         初始化：
         dp[begin][0] = 0
         dp[begin][1] = nums[begin]
         */
        int n = end-begin+1;
        //1 创建dp表
        int[][] dp = new int[n][2];
        //2 初始化
        dp[0][1] = nums[begin];
        //3 填表
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i+begin];
        }
        //4 返回值
        return Math.max(dp[n-1][0],dp[n-1][1]);
    }

    /**
     * 股票问题-归纳总结 */
    public int maxProfit(int[] prices) {
        /**
         状态表示：
         已知目前存在三种状态，分别是 可交易状态、买入状态、冷冻期状态等，故可设定状态表示如下：
         dp[i][0]表示在第i天时为可交易状态时，最大利润
         dp[i][1]表示在第i天时为买入状态时，最大利润
         dp[i][2]表示在第i天时为冷冻期状态时，最大利润
         状态转移方程：
         由状态机可得：
         dp[i][0] = max(dp[i-1][0],dp[i-1][2])
         dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])
         dp[i][2] = dp[i-1][1] + prices[i]
         初始化：
         对第一天进行初始化
         */
        int n = prices.length;
        //1 创建dp表
        int[][] dp = new int[n][3];
        //2 初始化
        dp[0][1] = -prices[0];
        //3 填表
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2] = dp[i-1][1] + prices[i];
        }
        //4 填表 - 返回三种状态的最大值
        return Math.max(Math.max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
    }
}
